package code;


public class KMP {
	public static int[] calFailure(StringBuffer pattern){
		
		int[] failure=new int[pattern.length()];
		int i,j;
		failure[0]=-1;
		/*
		 * 计算位置i的是匹配失败的最长前缀
		 * p[0...i]失败的最长前缀是p[0...failure[i]]
		 * 
		 */
		for(i=1,j=failure[0]=-1;i<pattern.length();i++){
			/*
			 * 递归查找位置i匹配失败的最长前缀
			 * j保存的是i-1位置的最长前缀
			 * 先比较pattern[i]与pattern[j+1]
			 * 如果失败的话，再找pattern[0...failure]试试
			 * 失败的话,在继续试，直到j=-1，说明没有相同的前缀
			 */
			while(j>=0 && pattern.charAt(i)!=pattern.charAt(j+1))
				j=failure[j];
			if(pattern.charAt(i)==pattern.charAt(j+1)) j++;
			failure[i]=j;
		}
		return failure;
	}
	public static void main(String[] args){
		int[] next=KMP.calFailure(new StringBuffer("abzabc"));
		for(int i=0;i<next.length;i++){
			System.out.println(next[i]);
		}
	}
}
